/*
https://leetcode.cn/problems/unique-binary-search-trees/description/
96. 不同的二叉搜索树
方钊堉 2024.10.19
区间dp
*/
class Solution {
public:
    // 计算不同结构的二叉搜索树的数量
    int numTrees(int n) {
        // 动态规划数组，G[numNodes] 表示有 numNodes 个节点的不同二叉搜索树的数量
        vector<int> numTreesDP(n + 1, 0);
        numTreesDP[0] = 1; // 空树的情况
        numTreesDP[1] = 1; // 只有一个节点的情况

        // 计算从 2 到 n 的所有节点数的情况
        for (int numNodes = 2; numNodes <= n; numNodes++) {
            // 枚举根节点的位置
            for (int root = 1; root <= numNodes; root++) {
                // 计算以 root 为根节点的不同二叉搜索树的数量
                numTreesDP[numNodes] += numTreesDP[root - 1] * numTreesDP[numNodes - root];
            }
        }

        return numTreesDP[n]; // 返回 n 个节点的不同二叉搜索树的数量
    }
};